package code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class WordLadderII {
	/*
	 * bfs一步步的搜索,start，end同时搜索
	 * map<a,parent>vis,a的父节点
	 */
	
	/*
	 * bfs一步步的搜索
	 * map<a,parent>vis,a的父节点
	 */
	
	public List<List<String>> findLadders(String start,String end,Set<String> dict){
		
		List<List<Integer>> edge=new ArrayList<List<Integer>>();
		ArrayList<String> nodeToString=new ArrayList<String>();
		Map<String,Integer> map=new HashMap<String,Integer>();
		
		if(!dict.contains(start))
			dict.add(start);
		if(!dict.contains(end))
			dict.add(end);
		Iterator it=dict.iterator();
		while(it.hasNext()){
			String s=(String) it.next();
			nodeToString.add(s);
			map.put(s, nodeToString.size()-1);
			edge.add(new ArrayList<Integer>());
		}
		
		it=dict.iterator();
		int i=0,j=0;
		/*
		 * 最主要原因是，以下n*n*len(s)长度的建立这个邻接表的时候，时间负责度最高
		 * 考虑到每个单词每个位置的只能有a~z的26个小写字母，所以枚举一个单词有一次变话的单词，查看以下字典里面是否有这些单词
		 * 这样的时间负责度26^len*一次查表的过程
		 */
		int index=0;
		while(it.hasNext()){
			String s=(String) it.next();
			char[] array=s.toCharArray();
			String ss;
			for(i=0;i<s.length();i++){
				char oldChar=array[i];
				for(j=0;j<26;j++){
					char newChar=(char)(j+'a');
					if(oldChar==newChar)
						continue;
					array[i]=newChar;
					ss=new String(array);
					if(dict.contains(ss)){
						edge.get(index).add(map.get(ss));
					}
				}
				array[i]=oldChar;
			}
			index++;
		}
		/*
		 * 从start开始bfs向end搜索
		 */
		Queue<Integer> queue=new LinkedList<Integer>();
		queue.add(map.get(start));
		
		List<List<String>> paths=new ArrayList<List<String>>();
		if(start.equals(end)){
			paths.add(new ArrayList<String>());
			paths.get(0).add(start);
			return paths;
		}
		
		int from=map.get(start);
		int to=map.get(end);
		int n=dict.size();
		int[] distance=new int[n];
		int[] revDistance=new int[n];
		
		int[] pre=new int[n];
		for(i=0;i<n;i++){
			distance[i]=n;
			revDistance[i]=n;
		}
		distance[from]=0;
		pre[from]=-1;
		int step=0;
		int finalDistance=-1;
		while(!queue.isEmpty()){
			int head=queue.poll();
//			System.out.println(nodeToString.get(head));
			List<Integer> ll;
			ll=edge.get(head);
			for(i=0;i<ll.size();i++){
				int clover=ll.get(i);
				//已经找到了path
				if(distance[clover]>distance[head]+1){
					distance[clover]=distance[head]+1;
					if(clover!=to)
						queue.add(clover);
					else{
						if(finalDistance==-1)	
							finalDistance=distance[clover];
					}
					
				}
			}
		}
		/*
		 * 逆搜一遍，找出在路径上的点
		 */
		queue.add(to);
		revDistance[to]=0;
		while(!queue.isEmpty()){
			int revHead=queue.poll();
			List<Integer> ll;
			ll=edge.get(revHead);
			for(i=0;i<ll.size();i++){
				int clover=ll.get(i);
				//已经找到了path
				if(revDistance[clover]>revDistance[revHead]+1){
					if(clover!=from)
						queue.add(clover);
					revDistance[clover]=revDistance[revHead]+1;
				}
			}
		}
		
		boolean[] used=new boolean[n];
		int u=from;
		pre=new int[n];
		pre[u]=-1;
		for(i=0;i<n;i++)	
			used[i]=false;
		used[u]=true;
		while(u!=-1){
			System.out.println(nodeToString.get(u));
			if(u==to){
				List<String> path=new ArrayList<String>();
				while(u!=-1){
					path.add(0, nodeToString.get(u));
					u=pre[u];
				}
				for(j=0;j<path.size();j++){
					System.out.print(path.get(j)+" ");
				}
				System.out.println();
				paths.add(path);
				u=from;
			}
			boolean blocked=true;
			for(i=0;i<edge.get(u).size();i++){
				int v=edge.get(u).get(i);
				if(!used[v] && distance[v]+revDistance[v]==finalDistance){
					pre[v]=u;
					used[v]=true;
					u=v;
					blocked=false;
					break;
				}
			}
			/*
			 * 遍历完次结点之后，回退
			 */
			if(blocked){
				u=pre[u];
			}
		}
		return paths;
	}
	public boolean isOneStep(String s,String t){
		if(s.length()!=t.length())	return false;
		if(s.equals(t))	return false;
		int i;
		for(i=0;i<s.length();i++){
			if(t.charAt(i)!=s.charAt(i))	
				break;
		}
		//一定有不一样的字符
		if(s.substring(i+1).equals(t.substring(i+1)))
			return true;
		return false;
	}
}